#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/types.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <sys/mman.h>

//currently only supports sorting of numbers
//suppose the data are already stored in column store and  binary format

struct sortObject{
	int key;
	int id;	
};

static void bubbleSort(struct sortObject *obj, int start,int num){

	for(int i=start;i<start+num-1;i++){
		struct sortObject tmp = obj[i];
		int pos = i;
		for(int j=i+1;j<start+num;j++){
			if(obj[j].key < tmp.key){
				tmp = obj[j];
				pos = j;
			}
		}
		obj[pos] = obj[i];
		obj[i] = tmp;
		
	}
}

// start to middle-1(inclusive) is the first part
// middle to end is the second part
// start, middle, and end are all array indexes

static void mergeSort(struct sortObject *obj, int start, int middle, int end){

	int firstNum = middle - start;
	int secondNum = end - middle + 1;

	if(firstNum > 1000){
		int mid = firstNum/2;
		mergeSort(obj, start, start+mid,middle-1);
	}else{
		bubbleSort(obj, start, firstNum);
	}

	if(secondNum > 1000){
		int mid = secondNum /2;
		mergeSort(obj, middle, middle+mid, end);
	}else{
		bubbleSort(obj, middle, secondNum);
	}

	struct sortObject * result = (struct sortObject *) malloc(sizeof(struct sortObject) * (end-start+1));
	if(!result){
		printf("Malloc failed in merge sort. Not enough memory.\n");
		exit(-1);
	}

	int i,j,k;
	for(i = start, j = middle, k=0; i<=middle-1 &&j<=end;){
		if(obj[i].key < obj[j].key){
			result[k++] = obj[i++];
		}else{
			result[k++] = obj[j++];
		}
	}

	while(i<=middle-1){
		result[k++] = obj[i++];
	}
	while(j<=end)
		result[k++] = obj[j++];

	memcpy(&obj[start],result, sizeof(struct sortObject)*(end-start+1));


	free(result);

}


// assumes all the columns from the same table stored on disk have the same prefiex(such as the table name)
// the only difference is the index 
// prerequsite: the memory should be large enough to hold all the elements from one column

int main(int argc, char **argv){

	char * path = "NEWLINEORDER";
	char * outPath = "FLINEORDER";
	int inFd;
	int primaryIndex, secondIndex,largestIndex;

	primaryIndex = 5;
	secondIndex = 4;
	largestIndex = 16; 

	char buf[32] = {0};

	sprintf(buf,"%s%d",path,primaryIndex);

	inFd = open(buf, O_RDONLY);
	int size = lseek(inFd,0,SEEK_END);
	int tupleNum = size/sizeof(int);

	char * primary = (char *) malloc(size);
	if(!primary){
		printf("Malloc failed. Not enough memory\n");
		exit(-1);
	}

	char *outTable =(char *) mmap(0,size,PROT_READ,MAP_SHARED,inFd,0);
        memcpy(primary,outTable,size);
        munmap(outTable,size);
        close(inFd);

	sprintf(buf,"%s%d",path,secondIndex);
	inFd = open(buf, O_RDONLY);
	size = lseek(inFd,0,SEEK_END);

	char * second = (char *) malloc(size);
	if(!second){
		printf("Malloc failed. Not enough memory\n");
		exit(-1);
	}

	outTable =(char *) mmap(0,size,PROT_READ,MAP_SHARED,inFd,0);
        memcpy(second,outTable,size);
        munmap(outTable,size);
        close(inFd);

	struct sortObject * obj = (struct sortObject *) malloc(sizeof(struct sortObject ) * tupleNum);

	if(!obj){
		printf("Malloc failed. Not enough memory!\n");
		exit(-1);
	}

	for(int i=0;i<tupleNum;i++){
		obj[i].key = ((int*)second)[i];
		obj[i].id = i;
	}

	free(second);

	int prev = ((int *)primary)[0];
	int prevPos = 0;
	int curr;
	int count = 1;

	for(int i=1;i<tupleNum;i++){
		curr = ((int *)primary)[i];
		if(curr == prev){
			count ++;
			continue;
		}else{
			int start = prevPos, middle = prevPos+ count/2, end = prevPos + count-1;
			mergeSort(obj,start,middle,end);
			count = 1;
			prev = curr;
			prevPos = i;
		}
	}

	if(count >1){
		int start = prevPos, middle = prevPos+ count/2, end = prevPos + count-1;
		mergeSort(obj,start,middle,end);
	}


	for(int i=0;i<= largestIndex;i++){

		if(i == primaryIndex)
			continue;

		sprintf(buf,"%s%d",path,i);
		inFd = open(buf,O_RDONLY);
		size = lseek(inFd,0,SEEK_END);
		int tupleSize = size/tupleNum;

		second = (char *) malloc(size);
		if(!second){
			printf("Malloc failed when trying to write the new result. Not enough memory !\n");
			exit(-1);
		}

		outTable = (char *) mmap(0,size,PROT_READ,MAP_SHARED,inFd,0);
		memcpy(second,outTable,size);
		munmap(outTable,size);

		sprintf(buf,"%s%d",outPath,i);
		int outFd = open(buf, O_RDWR|O_CREAT);

		for(int j=0;j<tupleNum;j++){
			int id = obj[j].id;
			write(outFd, second+id*tupleSize, tupleSize);
		}

		free(second);
		close(outFd);
	}

	free(obj);
	return 0;
}
